package Tree;

public class leet_105 {

}

class Solution_105 {
    /**
     * 跟进先序遍历与中序遍历构建二叉树
     * @param preorder  先序遍历
     * @param inorder   中序遍历
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        TreeNode root = buildTreeHelper(preorder, 0, preorder.length, inorder, 0, inorder.length);
        return root;
    }

    public TreeNode buildTreeHelper(int[] preOrder, int p_start, int p_end, int[] inOrder, int i_start, int i_end){
        /**
         * 思路： 先序遍历的序列每一个位置都是结点。所有按照先序遍历来把中序遍历的序列切分
         */
        if(p_start == p_end){
            // 已经递归到最后一层了，没有结点了
            return null;
        }

        // 找到根节点
        int rootValue = preOrder[p_start];
        TreeNode root = new TreeNode(rootValue);

        // 找到左子树的长度
        int i=i_start;
        for(; i<i_end; i++){
            int value = inOrder[i];
            if(rootValue == value){
                // 找到了中点，开始规定左右2边树的范围
                break;
            }
        }
        int leftNum = i-i_start;
        root.left = buildTreeHelper(preOrder, p_start+1, p_start+leftNum+1, inOrder, i_start, i);
        root.right = buildTreeHelper(preOrder, p_start +leftNum+1, p_end, inOrder, i+1, i_end);
        return root;
    }



}


